package BFS_733;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
	public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
		int color = image[sr][sc];
		if (color==newColor) {
			return image;
		}
		int rows = image.length;
		int cols = image[0].length;
		int[][] steps = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] { sr, sc });
		
		image[sr][sc] = newColor;
		while (!queue.isEmpty()) {
			int[] node = queue.poll();

			for (int i = 0; i < 4; i++) {
				int x = node[0] + steps[i][0];
				int y = node[1] + steps[i][1];

				if (x >= 0 && x < rows && y >= 0 && y < cols && image[x][y] == color) {
					image[x][y] = newColor;
					queue.add(new int[] { x, y });
				}

			}
		}
		return image;
	}
}
